Search Results

Documents authored by Meyer auf der Heide, Friedhelm

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.15
A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility

Authors: Jannik Castenow, Jonas Harbig, Daniel Jung, Peter Kling, Till Knollmann, and Friedhelm Meyer auf der Heide

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
We consider a swarm of n robots in a d-dimensional Euclidean space. The robots are oblivious (no persistent memory), disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task Gathering requires that all robots reach the same, not predefined position. In the related NearGathering task, they must reach distinct positions in close proximity such that every robot sees the entire swarm. In the considered setting, Gathering can be solved in 𝒪(n + Δ²) synchronous rounds both in two and three dimensions, where Δ denotes the initial maximal distance of two robots [Hideki Ando et al., 1999; Michael Braun et al., 2020; Bastian Degener et al., 2011]. In this work, we formalize a key property of efficient Gathering protocols and use it to define λ-contracting protocols. Any such protocol gathers n robots in the d-dimensional space in 𝒪(Δ²) synchronous rounds, for d ≥ 2. For d = 1, any λ-contracting protocol gathers in optimal time 𝒪(Δ). Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside the local convex hulls of their neighborhoods - λ-contracting protocols have this property - requires Ω(Δ²) rounds to gather all robots (d > 1). Among others, we prove that the d-dimensional generalization of the GTC-protocol [Hideki Ando et al., 1999] is λ-contracting. Remarkably, our improved and generalized runtime bound is independent of n and d. We also introduce an approach to make any λ-contracting protocol collision-free (robots never occupy the same position) to solve NearGathering. The resulting protocols maintain the runtime of Θ (Δ²) and work even in the semi-synchronous model. This yields the first NearGathering protocols for disoriented robots and the first proven runtime bound. In particular, combined with results from [Paola Flocchini et al., 2017] for robots with global visibility, we obtain the first protocol to solve Uniform Circle Formation (arrange the robots on the vertices of a regular n-gon) for oblivious, disoriented robots with limited visibility.
Cite as

Jannik Castenow, Jonas Harbig, Daniel Jung, Peter Kling, Till Knollmann, and Friedhelm Meyer auf der Heide. A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 15:1-15:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{castenow_et_al:LIPIcs.OPODIS.2022.15,
  author =	{Castenow, Jannik and Harbig, Jonas and Jung, Daniel and Kling, Peter and Knollmann, Till and Meyer auf der Heide, Friedhelm},
  title =	{{A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{15:1--15:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.15},
  URN =		{urn:nbn:de:0030-drops-176350},
  doi =		{10.4230/LIPIcs.OPODIS.2022.15},
  annote =	{Keywords: mobile robots, gathering, limited visibility, runtime, collision avoidance, near-gathering}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.22
Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets

Authors: Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
The modern warehouse is partially automated by robots. Instead of letting human workers walk into shelfs and pick up the required stock, big groups of autonomous mobile robots transport the inventory to the workers. Typically, these robots have an electric drive and need to recharge frequently during the day. When we scale this approach up, it is essential to place recharging stations strategically and as soon as needed so that all robots can survive. In this work, we represent a warehouse topology by a graph and address this challenge with the Online Connected Dominating Set problem (OCDS), an online variant of the classical Connected Dominating Set problem [Guha and Khuller, 1998]. We are given an undirected connected graph G = (V, E) and a sequence of subsets of V arriving over time. The goal is to grow a connected subgraph that dominates all arriving nodes and contains as few nodes as possible. We propose an O(log^2 n)-competitive randomized algorithm for OCDS in general graphs, where n is the number of nodes in the input graph. This is the best one can achieve due to Korman's randomized lower bound of Omega(log n log m) [Korman, 2005] for the related Online Set Cover problem [Alon et al., 2003], where n is the number of elements and m is the number of subsets. We also run extensive simulations to show that our algorithm performs well in a simulated warehouse, where the topology of a warehouse is modeled as a randomly generated geometric graph.
Cite as

Heiko Hamann, Christine Markarian, Friedhelm Meyer auf der Heide, and Mostafa Wahby. Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamann_et_al:LIPIcs.FUN.2018.22,
  author =	{Hamann, Heiko and Markarian, Christine and Meyer auf der Heide, Friedhelm and Wahby, Mostafa},
  title =	{{Pick, Pack, \& Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.22},
  URN =		{urn:nbn:de:0030-drops-88136},
  doi =		{10.4230/LIPIcs.FUN.2018.22},
  annote =	{Keywords: connected dominating set, online algorithm, competitive analysis, geometric graph, robot warehouse, recharging stations}
}
Document
DOI: 10.4230/DagSemProc.05361.1
05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks

Authors: Stefano Leonardi, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract
From 04.09.05 to 09.09.05, the Dagstuhl Seminar 05361 ``Algorithmic Aspects of Large and Complex Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Stefano Leonardi, Friedhelm Meyer auf der Heide, and Dorothea Wagner. 05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{leonardi_et_al:DagSemProc.05361.1,
  author =	{Leonardi, Stefano and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{05361 Abstracts Collection – Algorithmic Aspects of Large and Complex Networks}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.1},
  URN =		{urn:nbn:de:0030-drops-5702},
  doi =		{10.4230/DagSemProc.05361.1},
  annote =	{Keywords: Algorithms, Large and Complex Networks}
}
Document
DOI: 10.4230/DagSemRep.391
Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361)

Authors: Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner. Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361). Dagstuhl Seminar Report 391, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{adler_et_al:DagSemRep.391,
  author =	{Adler, Micah and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 03361)}},
  pages =	{1--5},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{391},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.391},
  URN =		{urn:nbn:de:0030-drops-152711},
  doi =		{10.4230/DagSemRep.391},
}
Document
DOI: 10.4230/DagSemRep.320
Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381)

Authors: Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Micah Adler, Friedhelm Meyer auf der Heide, and Dorothea Wagner. Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381). Dagstuhl Seminar Report 320, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{adler_et_al:DagSemRep.320,
  author =	{Adler, Micah and Meyer auf der Heide, Friedhelm and Wagner, Dorothea},
  title =	{{Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar 01381)}},
  pages =	{1--21},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{320},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.320},
  URN =		{urn:nbn:de:0030-drops-152041},
  doi =		{10.4230/DagSemRep.320},
}
Document
DOI: 10.4230/DagSemRep.246
Parallel and Distributed Algorithms (Dagstuhl Seminar 99291)

Authors: Bruce Maggs, Friedhelm Meyer auf der Heide, and Ernst W. Mayr

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Bruce Maggs, Friedhelm Meyer auf der Heide, and Ernst W. Mayr. Parallel and Distributed Algorithms (Dagstuhl Seminar 99291). Dagstuhl Seminar Report 246, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{maggs_et_al:DagSemRep.246,
  author =	{Maggs, Bruce and Meyer auf der Heide, Friedhelm and Mayr, Ernst W.},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 99291)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{246},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.246},
  URN =		{urn:nbn:de:0030-drops-151326},
  doi =		{10.4230/DagSemRep.246},
}
Document
DOI: 10.4230/DagSemRep.188
Parallel and Distributed Algorithms (Dagstuhl Seminar 9737)

Authors: Ernst W. Mayr, Friedhelm Meyer auf der Heide, and Larry Rudolph

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Ernst W. Mayr, Friedhelm Meyer auf der Heide, and Larry Rudolph. Parallel and Distributed Algorithms (Dagstuhl Seminar 9737). Dagstuhl Seminar Report 188, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{mayr_et_al:DagSemRep.188,
  author =	{Mayr, Ernst W. and Meyer auf der Heide, Friedhelm and Rudolph, Larry},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 9737)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{188},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.188},
  URN =		{urn:nbn:de:0030-drops-150752},
  doi =		{10.4230/DagSemRep.188},
}
Document
DOI: 10.4230/DagSemRep.125
Parallel and Distributed Algorithms (Dagstuhl Seminar 9537)

Authors: Cynthia Dwork, Ernst W. Mayr, and Friedhelm Meyer auf der Heide

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Cynthia Dwork, Ernst W. Mayr, and Friedhelm Meyer auf der Heide. Parallel and Distributed Algorithms (Dagstuhl Seminar 9537). Dagstuhl Seminar Report 125, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1995)

Copy BibTex To Clipboard

@TechReport{dwork_et_al:DagSemRep.125,
  author =	{Dwork, Cynthia and Mayr, Ernst W. and Meyer auf der Heide, Friedhelm},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 9537)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{1995},
  type = 	{Dagstuhl Seminar Report},
  number =	{125},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.125},
  URN =		{urn:nbn:de:0030-drops-150135},
  doi =		{10.4230/DagSemRep.125},
}
Document
DOI: 10.4230/DagSemRep.72
Parallel and Distributed Algorithms (Dagstuhl Seminar 9337)

Authors: Richard Cole, Ernst W. Mayr, and Friedhelm Meyer auf der Heide

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Richard Cole, Ernst W. Mayr, and Friedhelm Meyer auf der Heide. Parallel and Distributed Algorithms (Dagstuhl Seminar 9337). Dagstuhl Seminar Report 72, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)

Copy BibTex To Clipboard

@TechReport{cole_et_al:DagSemRep.72,
  author =	{Cole, Richard and Mayr, Ernst W. and Meyer auf der Heide, Friedhelm},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 9337)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1993},
  type = 	{Dagstuhl Seminar Report},
  number =	{72},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.72},
  URN =		{urn:nbn:de:0030-drops-149606},
  doi =		{10.4230/DagSemRep.72},
}
Document
DOI: 10.4230/DagSemRep.33
Parallel and Distributed Algorithms (Dagstuhl Seminar 9210)

Authors: Richard Cole, Ernst W. Mayr, and Friedhelm Meyer auf der Heide

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Richard Cole, Ernst W. Mayr, and Friedhelm Meyer auf der Heide. Parallel and Distributed Algorithms (Dagstuhl Seminar 9210). Dagstuhl Seminar Report 33, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1992)

Copy BibTex To Clipboard

@TechReport{cole_et_al:DagSemRep.33,
  author =	{Cole, Richard and Mayr, Ernst W. and Meyer auf der Heide, Friedhelm},
  title =	{{Parallel and Distributed Algorithms (Dagstuhl Seminar 9210)}},
  pages =	{1--23},
  ISSN =	{1619-0203},
  year =	{1992},
  type = 	{Dagstuhl Seminar Report},
  number =	{33},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.33},
  URN =		{urn:nbn:de:0030-drops-149216},
  doi =		{10.4230/DagSemRep.33},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact